import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=93 lang=java
 *
 * [93] 复原 IP 地址
 */

// @lc code=start
class Solution {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();

    public List<String> restoreIpAddresses(String s) {
        dfs(s, 0, 0);
        return res;
    }

    public void dfs(String s, int startIndex, int pointNum) {
        if (pointNum == 3) {// 分出四段了
            if (s.length() - startIndex <= 3) {
                String last = s.substring(startIndex, s.length());
                if (isValid(last)) {
                    path.append(last);
                    res.add(path.toString());
                    path.delete(path.length() - last.length(), path.length());//回溯
                }
            }
            return;
        }
        for (int i = startIndex; i < s.length() && i - startIndex < 3; i++) {
            String substr = s.substring(startIndex, i + 1);
            if (isValid(substr)) {
                path.append(substr);
                if (pointNum < 3) {
                    path.append(".");
                }
                pointNum++;
                dfs(s, i + 1, pointNum);
                pointNum--;
                if (pointNum < 3) {
                    path.deleteCharAt(path.length() - 1);// 去除点
                }
                path.delete(path.length() - substr.length(), path.length());// 去除substr
            } else {
                break;
            }
        }
    }

    private boolean isValid(String substr) {
        if (substr.length() > 1 && substr.charAt(0) == '0' || substr.equals("")) {
            return false;
        }
        int val = Integer.parseInt(substr);
        if (val > 255) {
            return false;
        }
        return true;
    }
}
// @lc code=end

//熟练后
// class Solution {
//     List<String> res=new ArrayList<>();
//     StringBuilder path=new StringBuilder();
//     public List<String> restoreIpAddresses(String s) {
//         dfs(s,0,0);
//         return res;
//     }

//     public void dfs(String s,int startIndex,int dotNum){
//         if(dotNum==3){
//             String last=s.substring(startIndex,s.length());
//             if(needed(last)){
//                 res.add(path.toString()+last);//path这里并没有变化
//                 return;
//             }
//         }

//         for(int i=startIndex;i<s.length()&& i - startIndex < 3;i++){
//             String tmp=s.substring(startIndex,i+1);
//             if(dotNum<3){
//                 if(needed(tmp)){
//                 path.append(tmp+".");          
//                 dfs(s,i+1,dotNum+1);
//                 path.delete(path.length()-tmp.length()-1,path.length());
//             }
//             }
            
//         }   
//     }

//     public boolean needed(String tmp){
//         if (tmp.length() > 1 && tmp.charAt(0) == '0' || tmp.equals("")) {
//             return false;
//         }
//         if(tmp.length()>3){
//             return false;
//         }
//         int val = Integer.parseInt(tmp);
//         if (val > 255) {
//             return false;
//         }
//         return true;
//     }
// }
